/* A Naive recursive implementation of 0-1 Knapsack problem */
/*
#include<stdio.h>
#include <stdlib.h>
// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
   // Base Case
   if (n == 0 || W == 0)
       return 0;

   // If weight of the nth item is more than Knapsack capacity W, then
   // this item cannot be included in the optimal solution
   if (wt[n-1] > W)
       return knapSack(W, wt, val, n-1);

   // Return the maximum of two cases:
   // (1) nth item included
   // (2) not included
   else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),
                    knapSack(W, wt, val, n-1)
                  );
}

// Driver program to test above function
int main()
{
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int  W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    printf("%d", knapSack(W, wt, val, n));
    return 0;
}
*/


// A Dynamic Programming based solution for 0-1 Knapsack problem
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define RANKNUM 5


int save(int *arr);
int build_data_and_cal();

int save(int *arr)
{
    char filename[15]="Knapsack.txt";
    FILE *fp;
    int i=0;
    if ((fp=fopen(filename,"a"))==NULL) //打开只写的文本文件
    {
        printf("cannot open file!");
        exit(0);
    }
    for (i=0;i<RANKNUM;i++){
        fprintf(fp , "%d" , *(arr+i) );
        fputs(",",fp);
    }
    fputs("\n",fp);
    fclose(fp); //关文件
    return 0;
}


// A utility function that returns maximum of two integers
int max(int a, int b) { return (a > b)? a : b; }

// Returns the maximum value that can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
   int i, w;
   int K[n+1][W+1];

   // Build table K[][] in bottom up manner
   for (i = 0; i <= n; i++)
   {
       for (w = 0; w <= W; w++)
       {
           if (i==0 || w==0)
               K[i][w] = 0;
           else if (wt[i-1] <= w)
                 K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]);
           else
                 K[i][w] = K[i-1][w];
       }
   }
   return K[n][W];
}


int build_data_and_cal(){
	srand((unsigned)time(NULL));
	int temp = 0;
	int j=0;
    int val[RANKNUM];
    int wt[RANKNUM];

	time_t c_start,c_end;

    // 随机产生物品价值数据
    for (j = 0; j < RANKNUM; j++)
    {
        temp = (rand() % (101))+1;    //产生1~101之间的随机价值,避免价值为0的物品
        val[j]=temp;
    }
    save(val);
    for (j = 0; j < RANKNUM; j++)
    {
        temp = (rand() % (50))+1;    //产生1~50之间的随机重量,避免重量为0的物品
        wt[j]=temp;
    }
    save(wt);

    int  W = 0;        //初始化总重量
    for (j = 0; j < RANKNUM; j++)
    {
        W+=wt[j];
    }
    if (W>200){
        temp = (rand() % (200))+200;    //产生1~300之间的随机去重重量,并避免重量被减为0
        W-=temp/2;
    }else{
        W/=2;
    }


    printf("knapsack total mass: %d\n",W);

    int n = sizeof(val)/sizeof(val[0]);

    c_start = clock();    //!<单位为ms
    printf("greatest value is : %d\n", knapSack(W, wt, val, n));

	c_end   = clock();
	printf("The pause used %f ms by clock()\n",difftime(c_end,c_start));
	return 0;
}


int main()
{
    build_data_and_cal();
    return 0;
}
